package a00_LeetCode.LinkedList;

/**
 * @Author quan
 * @Description 删除排序链表中的重复元素
 * 给定一个已排序的链表的头 head，删除原始链表中所有重复数字的节点，只留下不同的数字 。返回已排序的链表 。
 * @Date 2023/3/25 17:45
 */
public class Num82_DuplicatesSaveOne {
    /**
     * 主要思路：双指针法：创建一个虚拟头结点指向链表的头部head，第一个指针从dummyHead开始记作prev，第二个指针从虚拟头结点的下一个位置开始记作cur
     * 情况1：如果prev和cur的值不相等，说明不是重复的元素，就往后各移动一位；
     * 情况2：如果prev和cur的值相等，说明两者保存的是重复元素，就将prev记录的值进行保留，跳过cur保存的重复值，更改prev的指向为:直接指向cur的下一个节点。同时再更新cur的指向：往后移动一位
     * 终止条件：cur比prev快一步，所以当cur指向的值为null时，说明遍历结束
     */
    //普通方法
//    public ListNode deleteDuplicates(ListNode head) {
//        //(1)边界条件：只存在一个头结点或者不存在节点时，肯定不存在重复元素，直接返回头结点即可
//        if(head==null || head.next == null){
//            return head;
//        }
//        //(2)走到这里最少有两个节点存在
//        //创建一个虚拟头结点
//        ListNode dummyHead = new ListNode(-101);
//        //虚拟头结点添加到当前链表的最开始的头结点
//        dummyHead.next = head;
//        //创建一个头结点prev代替虚拟头结点从头开始
//        ListNode prev = dummyHead;//prev作为第一个指针
//        ListNode cur = prev.next;//cur作为第二个指针
//        //判断指针的值
//        while (cur!=null){
//            if(prev.val == cur.val){
//                prev = cur.next;
//            }else {
//                prev = prev.next;
//            }
//            cur = cur.next;
//        }
//        //返回链表的头结点
//        return dummyHead.next;
//    }
    /**
     * 递归法：先把以head为头结点的子链表的重复元素删除，保留一次（调用递归函数），
     * 再判断删除后的子链表的头结点与头结点head是否是重复元素，是的话删除head，返回子链表的头部，不是则返回head
     */
    public ListNode deleteDuplicates(ListNode head) {
        //(1)边界条件
        if(head==null || head.next == null){
            return head;
        }
        //先把以head为头结点的子链表的重复元素删除，保留一次
        head.next = deleteDuplicates(head.next);
        //现在剩下头结点
        return head.val == head.next.val ? head.next : head;
    }
}
